//
//  Graph.cpp
//  AdvPropTestsCpp
//
//  Created by Brian Bogard on 2/25/12.
//
//  --Revision History--
//
//
//  Copyright 2012 ASU. All rights reserved.
//

#include "Graph.h"
#include <boost/foreach.hpp>
#include <vector>
#include <algorithm>
#include <iostream>
#include <deque>

using namespace std;

Graph::Graph()
{
    m_coloredNodes[ Node::RED ] = boost::unordered_set< int >();
    m_coloredNodes[ Node::BLUE ] = boost::unordered_set< int >();
}

void Graph::showGraphInfo()
{
    BOOST_FOREACH( Graph::nodeMapType::value_type val, m_nodeMap )
    {
        string nodeColor = "white";
        if( val.second.getColor() == Node::RED )
        {
            nodeColor = "red";
        }
        else if( val.second.getColor() == Node::BLUE )
        {
            nodeColor = "blue";
        }
        cerr << "Node ID: " << val.first << ":" << nodeColor << endl;
    }
    cerr << "Edges:" << endl;
    BOOST_FOREACH( Graph::edgeMapType::value_type val, m_edgeMap )
    {
        cerr << "Node ID: " << val.first << endl;
        for( unsigned int index = 0; index < val.second.size(); ++index )
        {
            cerr << "\t->" << val.second[ index ] << endl;
        }
    }
}

Graph::Graph( const Graph & _graph )
{
    if( this != &_graph )
    {
        BOOST_FOREACH( Graph::nodeMapType::value_type val, _graph.m_nodeMap )
        {
            this->addNode( val.first, Node( val.first ) );
        }

        for(unsigned int index = 0; index < _graph.m_edgeSet.size(); ++index )
        {
            this->addEdge( _graph.m_edgeSet[ index ].get<0>(), _graph.m_edgeSet[ index ].get<1>());
        }
    }
}

Graph & Graph::operator=( const Graph & _graph )
{
    if( this == &_graph )
        return *this;
    
    BOOST_FOREACH( Graph::nodeMapType::value_type val, _graph.m_nodeMap )
    {
        this->addNode( val.first, Node( val.first ) );
    }
    for( int unsigned index = 0; index < _graph.m_edgeSet.size(); ++index )
    {
        this->addEdge( _graph.m_edgeSet[ index ].get<0>(), _graph.m_edgeSet[ index ].get<1>());
    }
    
    return *this;
}

void Graph::addNode( int _ID, Node _node )
{
    m_nodeMap[ _ID ] = _node;
    m_edgeMap[ _ID ] = vector< int >();
}

void Graph::addEdge( int _sourceNode, int _destNode )
{
    /*if( m_edgeMap.find( _sourceNode ) == m_edgeMap.end() )
    {
        m_edgeMap[ _sourceNode ] = vector< int >();
    }
    */
    m_edgeMap[ _sourceNode ].push_back( _destNode );
    /*
    if( m_edgeMap.find( _destNode ) == m_edgeMap.end() )
    {
        m_edgeMap[ _destNode ] = vector< int >();
    }
    */
    m_edgeMap[ _destNode ].push_back( _sourceNode );
    
    // For ease of computation later, we'll create a list of edges.
    // The order of source and destination aren't important as long as
    // there is only one unique edge per Pair
    m_edgeSet.push_back( boost::make_tuple( _sourceNode, _destNode ) );
}

void Graph::setNodeColor( int _ID, Node::COLOR _color )
{
    m_nodeMap[ _ID ].setColor( _color );
    m_coloredNodes[ _color ].insert( _ID );
}

Node::COLOR Graph::getNodeColor( int _ID )
{
    return m_nodeMap[ _ID ].getColor();
}

void Graph::resetNodeColor( int _ID )
{
    Node::COLOR currColor = m_nodeMap[ _ID ].getColor();
    
    if( currColor != Node::WHITE )
    {
        m_nodeMap[ _ID ].setColor( Node::WHITE );
        m_coloredNodes[ currColor ].erase( _ID );
    }
}

//BFB: This could be a very expensive copy when the graph is large, 
//     may want to create nodeMap on the heap
Graph::selectionMap Graph::degreeCentralityList( boost::shared_ptr< Graph > _graphObj )
{
    Graph::selectionMap nodeMap;
    
    BOOST_FOREACH( Graph::edgeMapType::value_type val, _graphObj->m_edgeMap )
    {
        nodeMap[ val.first ] = static_cast<double>( _graphObj->m_edgeMap[ val.first ].size() );
    }
    
    return nodeMap;
}

Graph::selectionMap Graph::DavidKempeSelection( boost::shared_ptr< Graph > _graphObj, int _maxDist )
{
    Graph::selectionMap nodeMap;
    
    for( unsigned int nodeNum = 0; nodeNum < _graphObj->m_nodeMap.size(); ++nodeNum )
    {
        nodeMap[ nodeNum ] = 1.0;
        boost::unordered_map< int, int > distanceFromRoot;
        distanceFromRoot[ nodeNum ] = 0;
        
        deque< int > exploreQueue;
        exploreQueue.push_back( nodeNum );
        while( exploreQueue.size() > 0 )
        {
            int currNode = exploreQueue.front();
            int currDistFromRoot = distanceFromRoot[ currNode ];
            exploreQueue.pop_front();
            if( distanceFromRoot[ currNode ] < _maxDist )
            {
                for( int edgeIndex = 0; edgeIndex < _graphObj->m_edgeMap[ currNode ].size(); ++edgeIndex )
                {
                    int neighborNode = _graphObj->m_edgeMap[ currNode ][ edgeIndex ];
                    if( distanceFromRoot.find( neighborNode ) == distanceFromRoot.end() )
                    {
                        nodeMap[ nodeNum ] += 1.0;
                        distanceFromRoot[ neighborNode ] = currDistFromRoot + 1;
                        exploreQueue.push_back( neighborNode );
                    }
                }
            }
        }
        
    }
    
    return nodeMap;

}

//BFB: This could be a very expensive copy when the graph is large, 
//     may want to create nodeMap on the heap
Graph::selectionMap Graph::closenessCentralityList( boost::shared_ptr< Graph > _graphObj )
{
    Graph::selectionMap nodeMap;
    double numOfNodes = static_cast<double>( _graphObj->m_nodeMap.size() );

    // Let's use a vector so it can do the allocation work for us
    vector< vector< double > > distances;
    for( unsigned int firstIndex = 0; firstIndex < _graphObj->m_nodeMap.size(); ++firstIndex )
    {
        distances.push_back( vector< double >() );
        for( unsigned int secondIndex = 0; secondIndex < _graphObj->m_nodeMap.size(); ++secondIndex )
        {
            distances[ firstIndex ].push_back( 0.0 );
            if( firstIndex == secondIndex )
            {
                distances[ firstIndex ].push_back( 0.0 );
            }
            else
            {
                distances[ firstIndex ].push_back( 1.0 );
            }       
        }
    }
    
    BOOST_FOREACH( Graph::edgeMapType::value_type val, _graphObj->m_edgeMap )
	{
		for( vector< int >::iterator iter = _graphObj->m_edgeMap[ val.first ].begin(); iter != _graphObj->m_edgeMap[ val.first ].begin(); ++iter )
		{
			distances[ val.first ][ *iter ] = 1.0 / numOfNodes;
		}
		nodeMap[ val.first ] = static_cast<double>( _graphObj->m_edgeMap[ val.first ].size() );
	}

    for( unsigned int outerIndex = 0; outerIndex <  _graphObj->m_nodeMap.size(); ++outerIndex )
    {
        for( unsigned int middleIndex = 0; middleIndex <  _graphObj->m_nodeMap.size(); ++middleIndex )
        {
            for( unsigned int innerIndex = 0; innerIndex <  _graphObj->m_nodeMap.size(); ++innerIndex )
            {
                distances[ middleIndex ][ innerIndex ] = min( distances[ middleIndex ][ innerIndex ], distances[ middleIndex ][ outerIndex ] + distances[ outerIndex ][ innerIndex ] );
            }
        }
    }
    
    for( unsigned int baseNode = 0; baseNode <  _graphObj->m_nodeMap.size(); ++baseNode )
    {
        int totalDist = 0;
        for( unsigned int destNode = 0; destNode < _graphObj->m_nodeMap.size(); ++destNode )
        {
            totalDist = totalDist + distances[ baseNode ][ destNode ];
        }
        nodeMap[ baseNode ] = totalDist;
    }
    
    return nodeMap;
}

void Graph::initializeActiveEdges( boost::shared_ptr< Graph > _graphObj, float _activeEdgeProb)
{
    edgeSetType _tempEdgeList;
    //Shahrzad added srand
    srand(time(NULL));
    for( edgeSetType::iterator iter = _graphObj->m_edgeSet.begin(); iter != _graphObj->m_edgeSet.end(); ++iter )
        {
            if( ( (float)rand() / (float)RAND_MAX ) < _activeEdgeProb )
            {
                _tempEdgeList.push_back( *iter );
            }
        }
    
    // Now let's reset the all edges in the graph
    _graphObj->m_edgeMap.clear();
    _graphObj->m_edgeSet.clear();
    cerr<<"New instance:"<<endl;
    for( edgeSetType::iterator iter = _tempEdgeList.begin(); iter != _tempEdgeList.end(); ++iter )
	{
		_graphObj->addEdge( (*iter).get<0>() , (*iter).get<1>() );
		cerr<<"Edge: "<<(*iter).get<0>()<<","<< (*iter).get<1>()<< " added"<<endl;
	}
}

Graph::nodeDistances Graph::getNodeDistances( boost::shared_ptr <Graph> _graphObj )
{
	//Shahrzad
	//This function was assigning 0 to all distances

    Graph::nodeDistances nodeDistMap;
    double numOfNodes = static_cast<double>( _graphObj->m_nodeMap.size() );
    
    // Let's use a vector so it can do the allocation work for us
    vector< vector< double > > distances;
    for( unsigned int firstIndex = 0; firstIndex < _graphObj->m_nodeMap.size(); ++firstIndex )
    {
        distances.push_back( vector< double >() );
        for( unsigned int secondIndex = 0; secondIndex < _graphObj->m_nodeMap.size(); ++secondIndex )
        {
//            distances[ firstIndex ].push_back( 0.0 );
            if( firstIndex == secondIndex )
            {
                distances[ firstIndex ].push_back( 0.0 );
            }
            else
            {
//                distances[ firstIndex ].push_back( 1.0 );
            	distances[ firstIndex ].push_back( numOfNodes );
            }       
        }
    }
    
    BOOST_FOREACH( Graph::edgeMapType::value_type val, _graphObj->m_edgeMap )
    {
    	//Shahrzad changed iter != _graphObj->m_edgeMap[ val.first ].begin() to iter != _graphObj->m_edgeMap[ val.first ].end()
        for( vector< int >::iterator iter = _graphObj->m_edgeMap[ val.first ].begin(); iter != _graphObj->m_edgeMap[ val.first ].end(); ++iter )
        {
  //          distances[ val.first ][ *iter ] = 1.0 / numOfNodes;
        	distances[ val.first ][ *iter ] = 1.0;
        }
    }
    
    for( unsigned int outerIndex = 0; outerIndex <  _graphObj->m_nodeMap.size(); ++outerIndex )
    {
        for( unsigned int middleIndex = 0; middleIndex <  _graphObj->m_nodeMap.size(); ++middleIndex )
        {
            for( unsigned int innerIndex = 0; innerIndex <  _graphObj->m_nodeMap.size(); ++innerIndex )
            {
                distances[ middleIndex ][ innerIndex ] = min( distances[ middleIndex ][ innerIndex ], distances[ middleIndex ][ outerIndex ] + distances[ outerIndex ][ innerIndex ] );
            }
        }
    }
    
    //SHAHRZAD-debug
/*    for( unsigned int Index1 = 0; Index1 <  _graphObj->m_nodeMap.size(); ++Index1 )
     {
         for( unsigned int Index2 = 0; Index2 <  _graphObj->m_nodeMap.size(); ++Index2 )
         {
        	 cerr<<"distance between nodes "<<Index1<<" and "<<Index2<<" is "<<distances[Index1][Index2]<<endl;
         }
     }*/

    
    for( unsigned int baseNode = 0; baseNode < _graphObj->m_nodeMap.size(); ++baseNode )
    {
        boost::unordered_map< int, vector< int > > distMap;

        for( unsigned int destNode = 0; destNode < _graphObj->m_nodeMap.size(); ++destNode )
        {
            int distance = distances[ baseNode ][ destNode ];
            if( distMap.find( distance ) == distMap.end() )
            {
                distMap[ distance ] = vector< int >();
            }
            
            distMap[ distance ].push_back( destNode );
            
        }

        nodeDistMap[ baseNode ] = distMap;
    }
    
    return nodeDistMap;
}

double Graph::propagate( boost::shared_ptr<Graph> _graphObj, int maxPropagationDist)
{
    // We'll subtract 1 for every red node created, we'll add 1 for every blue node
    double nodeColorDiff = 0;
    
    //Shahrzad: We don't need the random 
    // Random generator = new Random();
    
    // We'll have to get all of the node distances first


    Graph::nodeDistances nodeDists = getNodeDistances( _graphObj );
    
    for( unsigned int nodeID = 0; nodeID < _graphObj->m_nodeMap.size(); ++nodeID )
    {
    	_graphObj->getNodeColor( nodeID );
        // If this node is already a different color, we'll just count it
        if( _graphObj->getNodeColor( nodeID ) == Node::RED )
        {
            nodeColorDiff -= 1.0;
            continue;
        }
        else if( _graphObj->getNodeColor( nodeID ) == Node::BLUE )
        {
            nodeColorDiff += 1.0;
            continue;
        }
        
        int redInfluence = 0;
        int blueInfluence = 0;
//Shahrzad: here we should replace _graphObj->m_nodeMap.size() with the propagation step d that we discussed before
     //   for( unsigned int distance = 1; distance < _graphObj->m_nodeMap.size() ;++distance )
        for( unsigned int distance = 1; distance < maxPropagationDist ;++distance )
        {
          //  typedef boost::unordered_map< int, boost::unordered_map< int, vector< int > > > nodeDistances;
        	cerr<<"Checking  "<<distance <<" neighborhood of "<<nodeID<< endl;
            // If there's nothing inthis set, move on
            if( nodeDists[ nodeID ].find( distance ) == nodeDists[ nodeID ].end() )
                continue;
            
            for( vector< int >::iterator iter = nodeDists[ nodeID ][ distance ].begin(); iter != nodeDists[ nodeID ][ distance ].end(); ++iter )
            {

                if( _graphObj->m_coloredNodes[ Node::RED ].find( *iter ) != _graphObj->m_coloredNodes[ Node::RED ].end() )
                    ++redInfluence;
                else if( _graphObj->m_coloredNodes[ Node::BLUE ].find( *iter ) != _graphObj->m_coloredNodes[ Node::BLUE ].end() )
                    ++blueInfluence;
            }
            cerr<<"Node "<<nodeID<< " is influenced by "<<redInfluence<< " red nodes at distance "<< distance<<endl;
            cerr<<"Node "<<nodeID<< " is influenced by "<<blueInfluence<< " blue nodes at distance "<< distance<<endl;
            // If we found any influencing nodes, we'll break and figure out the winner later 
            if( ( redInfluence > 0 ) || ( blueInfluence > 0 ) )
                break;  
        }
        
        if( ( redInfluence > 0 ) || ( blueInfluence > 0 ) )
        {
        	//Shahrzad: we do not need the if statement;
        	 nodeColorDiff += static_cast<double>( (blueInfluence - redInfluence ) ) / static_cast<double>( ( blueInfluence + redInfluence ) );
        	/*  if( blueInfluence == 0 )
            {
                --nodeColorDiff;
            }
            else if( redInfluence == 0 )
            {
                ++nodeColorDiff;
            }
            else
            {
                nodeColorDiff += static_cast<double>( (blueInfluence - redInfluence ) ) / static_cast<double>( ( blueInfluence + redInfluence ) );
            }*/
            
        }
        
    }
    
    return nodeColorDiff;
}
